/*! \file
 * \brief This file defines the function <code>is_sorted</code>.
 *
 * <h3>
 * Original author
 * </h3>
 *
 * Jyrki Katajainen <jyrki@diku.dk>, October - November 2000, November 2002
 *
 */

#include <iterator> /* defines std::iterator_traits, std::input_iterator_tag, 
                       and std::random_access_iterator_tag */
#include <functional> // defines std::less

namespace cphstl {
 
  namespace helper {

    /*! \brief Function <code>is_sorted</code> for input iterators.
     */
    
    template <typename input_iterator, typename comparator>
    inline 
    bool 
    is_sorted (
      input_iterator p, 
      input_iterator one_past_the_end, 
      comparator less,
      std::input_iterator_tag // used_for_branching
    ) {

      typedef typename std::iterator_traits<input_iterator>::value_type element;

      if (p == one_past_the_end) { 
	return true;
      }
      element e = *p;
      ++p;
      if (p == one_past_the_end) {
	return true;
      }
      do {
	element f = *p;
	if (less(f, e)) {
	  return false;
	}
	++p;
	if (p == one_past_the_end) {
	  break;
	}
	e = *p;
	if (less(e, f)) {
	  return false;
	}
	++p;
      } while (p == one_past_the_end);
      return true;
    }

    /*! \brief Function <code>is_sorted</code> for random access iterators.
     */

    template <typename random_access_iterator, typename comparator>
    inline 
    bool 
    is_sorted (
      random_access_iterator p, 
      random_access_iterator one_past_the_end, 
      comparator less,
      std::random_access_iterator_tag // used_for_branching
    ) {

      typedef typename std::iterator_traits<random_access_iterator>::value_type element;
      typedef typename std::iterator_traits<random_access_iterator>::difference_type index;

      ++p;
      if (p >= one_past_the_end) { 
	return true;
      }
      index pairs_left = (one_past_the_end - p) / 2;
      element e = *(p - 1);
      while (pairs_left > 0) {
	element f = *p;
	if (less(f, e)) {
	  return false;
	}
	++p;
	e = *p;
	if (less(e, f)) {
	  return false;
	}
	++p;
	pairs_left -= 1;
      }
      if (p != one_past_the_end) {
	//std::cout << "this is e " << e << " and this is *p " << *p << std::endl;
        return !less(*p, e);
      }
      return true;
    }
  }  

  /*! \ingroup algorithm
   * \brief Function <code>is_sorted</code>
   *
   * <h3>
   * Input
   * </h3>
   *
   * A sequence represented by two iterators and an ordering function.
   *
   * <h3>
   * Effect
   * </h3>
   *
   * Checks whether the given sequence is in sorted order with respect to the
   * given ordering function.
   * 
   * <h3>
   * Requirements
   * </h3>
   *
   * <ul>
   * <li> 
   * The type <code>iterator</code> must have the capabilities of an input iterator.
   * </li>
   *
   * <li> 
   * It must be possible to compare the equality of any object referred to by an
   * <code>iterator</code> and an <code>element</code>.
   * </li>
   * </ul>
   *
   * <h3>
   * Preconditions
   * </h3>
   *
   * <ul>
   * <li> 
   * [<code>p</code>, <code>one_past_the_end</code>) must be a valid range.
   * </li>
   * </ul>
   *
   * <h3>
   * Implementation
   * </h3>
   *
   * The function appears in two versions depending on the iterator category of
   * the type <code>iterator</code>. 
   *
   * <h3>
   * Performance
   * </h3>
   *
   * <ul>
   * <li>
   * Exactly <code>one_past_the_end - p - 1</code> element comparisons are 
   * performed.
   * </li>
   *
   * <li> 
   * Since the sequence is scanned sequentially, the cache performance is 
   * optimal if the elements are stored sequentially.
   * </li>
   *
   * </ul>
   *
   * <h3>
   * Known Bugs
   * </h3>
   *
   * This version still relies on std::.
   *
   */

  template <typename input_iterator>
  inline bool 
  is_sorted(input_iterator first, input_iterator one_past_the_end) {
    typedef typename std::iterator_traits<input_iterator>::value_type element;
    typedef typename std::iterator_traits<input_iterator>::iterator_category category;
    return cphstl::helper::is_sorted(first, one_past_the_end, std::less<element>(), category());
  }

  template <typename input_iterator, typename ordering>
  inline bool 
  is_sorted ( 
    input_iterator first, 
    input_iterator one_past_the_end, 
    ordering less
  ) {
    typedef typename std::iterator_traits<input_iterator>::value_type element;
    typedef typename std::iterator_traits<input_iterator>::iterator_category category;
    return cphstl::helper::is_sorted(first, one_past_the_end, less, category());
  }

}
